//
// Created by andrew on 2024/9/21.
//

#include <string>
#include <vector>
#include <unordered_set>

#include <iostream>
#include <gtest/gtest.h>


using namespace std;


class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length() < 2) return s;

        int start = 0, end = 0;
        for (int i = 0; i < s.length(); ++i) {
            // 从一个点扩展
            int len1 = expandAroundCenter(s, i, i);
            // 从两个点扩展
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }

    int expandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
};

class Solution1 {
public:
    string longestPalindrome(string s) {
        // 如果只有一个字符，直接返回当前字符串
        if (s.length() < 2) return s;

        int start = 0, end = 0;
        for (int i = 0; i < s.length(); ++i) {
            // 中心触发 left == right
            auto len1 = expandAroundCenter(s, i, i);
            auto len2 = expandAroundCenter(s, i, i + 1);
            auto len = std::max(len1, len2);

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substr(start, end - start + 1);
    }

    int expandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            -- left;
            ++ right;
        }
        return right - left - 1;
    }

};



class Solution2 {
public:
    string longestPalindrome(string s) {
        // 如果只有一个字符，直接返回当前字符串
        if (s.length() < 2) {
            return s;
        }

        int strLen = s.length();
        // 回文字符串的起始点
        int start = 0;
        // 回文字符串的结束点
        int end = 0;
        // 回文字符串的长度
        int maxLength = 1;

        bool **dp = new bool*[strLen];
        for (int i = 0; i < strLen; i++) {
            dp[i] = new bool[strLen];
        }

        for (int i = 0; i < strLen; i++) {
            for (int j = 0; j < strLen; j++) {
                dp[i][j] = false;
            }
        }

        for (int r = 1; r < strLen;  ++r) {
            for (int l = 0; l < r; ++l) {
                // 递进， l==r 并且能被赋值为true的前提是dp[l+1][r-1]为true
                if (s[l] == s[r] && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLength) {
                        maxLength = r - l + 1;
                        start = l;
                        end = r;
                    }
                }
            }
        }
        return s.substr(start, end + 1 - start);
    }
};








TEST(leetcode5, leetcode) {

    string s = "babad";
    Solution solution;

    ASSERT_EQ(solution.longestPalindrome(s)  , "aba");
}
